#include <iostream>
#include <unordered_map>
using namespace std;

// 146.LRU缓存
// 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
//实现 LRUCache 类：
// LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
// int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
// void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
// 双向链表结点
struct DLNode {
    int key,val;
    DLNode* pre;
    DLNode* next;
    DLNode(int _key,int _val):key(_key),val(_val),pre(nullptr),next(nullptr) {}
};
class LRUCache {
private:
    unordered_map<int, DLNode*> cache;  // 用unordered_map作为哈希表，速度更快
    DLNode* head;   // 虚拟头结点
    DLNode* tail;   // 虚拟尾结点
    int size;       // 实际大小
    int capacity;   // 容量
public:
    LRUCache(int capacity):capacity(capacity),size(0) {
        head = new DLNode(0,0);
        tail = new DLNode(0,0);
        head->next = tail;
        tail->pre = head;
    }
    // 访问
    int get(int key) {
        if(cache.count(key) == 0) {
            return -1;  // 如果不存在，则返回-1
        }
        DLNode *p = cache[key];
        moveToHead(p);  // 将p结点移动到缓存头部
        return p->val;  // 返回其值
    }
    // 将数据放入缓存
    void put(int key, int value) {
        if(cache.count(key) == 0) { // 缓存中没有数据
            if(capacity == size) {  // 缓存已满
                DLNode *q = removeTail();   // 删除尾结点
                cache.erase(q->key);     // 删除哈希表对应项
                delete q;   // 释放尾结点
                --size;
            }
            // 将新结点放到表头
            auto p = new DLNode(key,value);
            addToHead(p);   // 放入链表中头部
            cache[key] = p; // 添加到哈希表
            ++size;
        } else {    // 缓存中已经存在key
            DLNode *p = cache[key];
            p->val = value; // 更新值
            moveToHead(p);  // 移动到链表的头部
        }
    }

private:
    void addToHead(DLNode* p) { // 添加p结点到链表头部
        p->next = head->next;
        p->pre = head;
        head->next->pre = p;
        head->next = p;
    }
    void removeNode(DLNode *p) {    // 删除p结点
        p->pre->next = p->next;
        p->next->pre = p->pre;
    }
    void moveToHead(DLNode *p) {    // 移动p结点到链表头部
        removeNode(p);  // 先删除
        addToHead(p);   // 再添加
    }
    DLNode* removeTail() {  // 删除尾结点
        DLNode* p = tail->pre;
        removeNode(p);
        return p;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
int main() {
    LRUCache cache1(2);
    cache1.put(1, 1);
    cache1.put(2, 2);
    cout << cache1.get(1) << endl; // 1
    cache1.put(3, 3);
    cout << cache1.get(2) << endl; // -1
    cache1.put(4, 4);
    cout << cache1.get(1) << endl; // -1
    cout << cache1.get(3) << endl; // 3
    cout << cache1.get(4) << endl; // 4

    cout << endl;

    LRUCache cache2(2);
    cache2.put(2, 1);
    cache2.put(1, 1);
    cache2.put(2, 3);
    cache2.put(4, 1);
    cout << cache2.get(1) << endl; // -1
    cout << cache2.get(2) << endl; // 3

    return 0;
}
